package P215;

import org.junit.Test;

/**
 * @Author DJ同学
 * @Date 2021/3/2 18:16
 * @Version 1.0
 * @Name 数组中的第K个最大元素
 * @Problem https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 * 使用堆
 */
public class Solution {

    @Test
    public void test(){
        int[] ints = {3, 2, 1, 5, 6, 4};
        System.out.println(findKthLargest(ints,2));
    }
    Integer[] minHeap;
    int size = 0;
    public int findKthLargest(int[] nums, int k) {
//        执行k次放入堆中
        minHeap = new Integer[nums.length+1];
        minHeap[0]=Integer.MIN_VALUE;
        int i = 0;
        for (; i < k; i++) {
           add(nums[i]);
        }
        for (; i < nums.length; i++) {
            add(nums[i]);
            delete();
        }
        return minHeap[1];
    }
    void add(Integer num){
        minHeap[++size] = num;
        int j = size;
        for(;num<minHeap[j/2];j/=2){
            minHeap[j] = minHeap[j/2];
        }
        minHeap[j] = num;
    }
    void delete(){
        int temp = minHeap[size--];
        int parent=1;
        int child=2*parent;
        while(child<=size){

            if(child+1<=size&&minHeap[child+1]<minHeap[child]){
                child++;
            }
            if(temp>minHeap[child]){
                minHeap[parent] = minHeap[child];
                parent = child;
                child=2*parent;
                continue;
            }else{
                break;
            }

        }
        minHeap[parent] = temp;
    }
}
